package Algorithm.String.TrieTree;

//https://leetcode-cn.com/problems/map-sum-pairs/

import sun.text.normalizer.Trie;

import java.util.HashMap;
import java.util.Map;

public class Leetcode677 {

    static class MapSum {

        public static class TrieNode{
            TrieNode[] next = new TrieNode[26];
            int value;
        }

        Map<String, Integer> map = new HashMap<String, Integer>();
        TrieNode root = new TrieNode();

        public MapSum() {

        }

        public void insert(String key, int val) {
            int delta = val - map.getOrDefault(key, 0);
            map.put(key,val);
            TrieNode node = root;
            for(char c : key.toCharArray()){
                if(node.next[c-'a']==null){
                    node.next[c-'a'] = new TrieNode();
                }
                node = node.next[c-'a'];
                node.value = node.value + delta;
                // System.out.println(node.value);
            }
        }

        public int sum(String prefix) {
            TrieNode node = root;
            for(int i=0;i<prefix.length();i++){
                if(node.next[prefix.charAt(i)-'a']!=null&&node.next[prefix.charAt(i)-'a'].value>0){
                    if(i==prefix.length()-1)
                        return node.next[prefix.charAt(i)-'a'].value;
                    else
                        node = node.next[prefix.charAt(i)-'a'];
                }else{
                    return 0;
                }
            }
            return 0;
        }
    }

}
